package primary;

import java.util.Arrays;

/**
 * 集合的相关概念
 * <p>
 * List 是有序可重复（有下标索引）
 * <p>
 * 1. 不需要线程安全 ，查找操作多，建议使用ArrayList
 * 2. 不需要线程安全，增加删除操作多，建议使用LinkedList
 * 3. 需要线程安全，建议使用Vector，效率较低
 *
 *
 *
 * <p>
 * Set无序不可重复
 */
public class L_Collections {

    public static void main(String[] args) {
        SxArrayList sa = new SxArrayList<String>();
        sa.add("aa");
        sa.add("yeung");
        sa.add(32);
        System.out.println(sa.toString());
        System.out.println("-------map test------------");
        SxMap<String, Integer> map = new SxMap<String, Integer>();
        map.put("4", 32);
        map.put("32", 33);
        System.out.println(map.toString());
        System.out.println("test map get:" + map.get("4"));
        System.out.println("test map get:" + map.get("100"));
    }

    /**
     * 自定义ArrayList 集合
     */
    static class SxArrayList<E> {
        private Object[] elements;
        private int size;
        private static final int DEFAULT_CAPACITY = 10;

        public SxArrayList() {
            elements = new Object[DEFAULT_CAPACITY];
        }

        public SxArrayList(int capacity) {
            elements = new Object[capacity];
        }

        public void add(E ele) {
            if (size == elements.length) {
                //需要扩容了
                Object[] newArr = new Object[elements.length + (elements.length >> 1)];//增加50%空间
                System.arraycopy(elements, 0, newArr, 0, elements.length);
                elements = newArr;
            }
            elements[size++] = ele;
        }

        public E get(int index) {
            return (E) elements[index];
        }

        public void remove(int index) {
            if (checkRange(index)) {
                int numMoved = elements.length - index - 1;
                if (numMoved > 0)//是否需要拷贝数据
                    System.arraycopy(elements, index + 1, elements, index, numMoved);
                elements[size--] = null;
                size--;
            }
        }

        public int indexOf(E ele) {
            int index = -1;
            for (int i = 0; i < elements.length; i++) {
                if (elements[i].equals(ele)) {
                    index = i;
                    break;
                }
            }
            return index;
        }

        public void remove(E ele) {
            for (int i = 0; i < size; i++) {
                if (elements[i].equals(ele)) {
                    //删除数据
                    int index = indexOf(ele);
                    if (index != -1) {
                        remove(index);
                    }
                }
            }
        }

        /**
         * 判断下标是否有效
         *
         * @param index
         * @return
         */
        public boolean checkRange(int index) {
            if (index < 0 || index > size) return false;
            else return true;
        }

        @Override
        public String toString() {
            return Arrays.toString(elements);
        }
    }

    static class SxMap<K, V> {
        SxNode[] table;// 位桶数组
        int size;//存放键值对的个数

        public SxMap() {
            table = new SxNode[16];//长度一般定义为2的整数瞑
        }

        public void put(K key, V v) {
            SxNode sn = new SxNode();
            sn.hash = sxHash(key.hashCode(), table.length);
            sn.key = key;
            sn.value = v;
            sn.next = null;
            //添加元素
            SxNode tmp = table[sn.hash];//获取该位置的值
            SxNode iterLast = null;
            if (tmp == null) {
                //此处数组元素为空，则直接将新节点放进去
                table[sn.hash] = sn;
            } else {
//                元素不为空
                while (tmp != null) {
                    if (tmp.key.equals(key)) {
                        System.out.println("key值唯一");
                    } else {
                        iterLast = tmp;
                        tmp = tmp.next;
                    }
                }

                iterLast.next = sn;
            }
        }

        public V get(K key) {
            int hashCode = sxHash(key.hashCode(), table.length);
            SxNode kv = table[hashCode];
            V result = null;
            if (kv != null)
                do {
                    //找到有改key
                    if (kv.key.equals(key)) {
                        result = (V) kv.value;
                        break;
                    }
                    if (kv.next == null) break;
                    kv = kv.next;

                } while (true);
            return result;
        }

        private SxNode last(SxNode[] table, int hashIndex) {
            SxNode ls = null;
            for (SxNode sxNode : table) {
                if (sxNode.next == null) {
                    ls = sxNode;
                    break;
                }
            }
            return ls;
        }

        public int sxHash(int v, int length) {
            return v & (length - 1);
        }

        @Override
        public String toString() {
            return Arrays.toString(table);
        }
    }

    /**
     * 节点类，可用于map 和LinkedList 的自定义实现
     */
    static class SxNode {
        int hash;
        Object key;
        Object value;
        SxNode next;

        @Override
        public String toString() {
            return "SxNode{" +
                    "hash=" + hash +
                    ", key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    '}';
        }
    }
}
